#include <list>
struct Node {
  int val;
  Node *left;
  Node *right;
  Node(int val) : val(val), left(nullptr), right(nullptr) {}
};
struct Node1 {
  int val;
  Node1 *left;
  Node1 *right;
  Node1 *parent;
  Node1(int val) : val(val), left(nullptr), right(nullptr), parent(nullptr) {}
};
int maxwidtree(Node *head) {
  if (head == nullptr)
    return 0;

  std::list<Node *> queue;
  Node *nowend = nullptr;
  Node *nextend = nullptr;
  int res = 0;
  int tempres = 0;
  queue.push_back(head);
  nowend = head;
  while (!queue.empty()) {
    Node *p = queue.front();
    if (p->left) {
      queue.push_back(p->left);
      nextend = p->left;
    }
    if (p->right) {
      queue.push_back(p->right);
      nextend = p->right;
    }
    ++tempres;
    if (p == nowend) {
      if (tempres > res) {
        res = tempres;
      }
      nowend = nextend;
      nextend = nullptr;
      tempres = 0;
    }
    queue.pop_front();
  }
  return res;
}

Node1 *getleftest(Node1 *head) {
  if (head == nullptr)
    return nullptr;
  Node1 *p = head;
  while (p->left) {
    p = p->left;
  }
  return p;
}

Node1 *findnext(Node1 *head) {
  if (head == nullptr)
    return nullptr;
  if (head->right) {
    return getleftest(head->right);
  } else {
    Node1 *parent = nullptr;
    Node1 *now = head;
    while ((now != nullptr)) {
      parent = now->parent;
      if ((parent == nullptr) || (parent->left == now)) {
        return parent;
      } else {
        now = parent;
      }
    }
    return nullptr;
  }
}

int main()
{
}
